package leetcode;

/**
 * Created with IntelliJ IDEA.
 * User: Ghost
 * Date: 14-6-13
 * Time: 下午7:44
 * To change this template use File | Settings | File Templates.
 */
public class Maximum_Subarray {
    public int maxSubArray(int[] A) {
        if(A.length==0){
            return 0;
        }
        int MaxSum = A[0];
        int[] AA = new int[A.length+1];
        AA[0] = 0;
        for(int i=1;i<AA.length;i++){
            AA[i] = A[i-1];
        }
        int[] B = new int[AA.length];
        B[0] = 0;
        for(int i=1;i<AA.length;i++){
            if(B[i-1]>0){
                B[i] = B[i-1]+AA[i];
            }
            else
                B[i] = AA[i];
            if(MaxSum<B[i]){
                MaxSum = B[i];
            }
        }
        return MaxSum;
    }
    public static void main(String[] args){
        Maximum_Subarray maximum_subarray = new Maximum_Subarray();
        int[] a = {-2,1,-3,4,-10,2,1,-5,4};
        System.out.println(maximum_subarray.maxSubArray(a));
    }
}
